LZ77 is an extremely common reversible data compression algorithm developed by Lempel and Ziv in 1977. The principle of LZ77 is sliding dictionary-type compression. The LZ77, while moving a pointer from the beginning to the end of a character string stream, searches for the longest match to a character string that starts from the current pointer in a character string stream of a prescribed length in the past from the current pointer (called a sliding dictionary). In addition, the LZ77 reduces the amount of data in a character string stream by converting the character string indicated by the current pointer to copy symbols, and compresses the character string stream. In addition to having a simple principle and being easy to implement, the LZ77 is also known for having relatively good compressibility. The size of the sliding dictionary is arbitrary, and a larger size sliding dictionary increases the probability of matching a character string, thereby improving compressibility.
Storage systems for storing and managing large amounts of data are being equipped with data compression functions to make it possible to lower per-capacity-cost when larger amounts of data are being stored. Storage systems are classified into two types: file storage for managing data in file units, and block storage for managing data in fixed-size sector units. Regardless of the type of storage system, the compression methods being employed in the data compression functions are by and large the above-described LZ77, or an algorithm derived from the LZ77.
Patent Literature 1 discloses a technique for the high-speed decompression of data compressed on the basis of the LZ77. A parallelization technique for decompressing compressed data at high speed by processing software using a general-purpose processor is also disclosed in Patent Literature 1. This technique divides plaintext data to be compressed into a plurality of blocks and compresses each block. The number of blocks is determined on the basis of the parallel processing capabilities of the processor (number of cores and so forth) used at decompression.